package leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-21 13:50
 **/
public class LeetCode84 {

    //单调栈+常数优化
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        //为右边界数组赋默认值n,下面优化了,不会单遍历判断一次右边界
        Arrays.fill(right, n);

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            //如果当前值<=栈顶元素,能够确定栈顶元素的右边界是当前索引处的值
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                right[stack.peek()] = i;
                stack.pop();
            }
            left[i] = (stack.isEmpty() ? -1 : stack.peek());
            stack.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }

        return res;
    }


    //单调栈
    /*public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        //left[i]: 左边<heights[i]的最大索引
        int[] left = new int[n];
        //right[i]: 右边<heights[i]的最小索引
        int[] right = new int[n];

        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; ++i) {
            //如果栈非空,且height[i]<=栈顶元素,栈顶元素出栈
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }

            //如果栈为空,left[i]=-1, 否则就是栈顶元素
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }

            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int res = 0;
        //思想同暴力破解,遍历,求出每个下标左右可以扩展的最大矩形面积
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }

        return res;
    }*/

    //暴力
    /*public int largestRectangleArea(int[] heights) {
        int n = heights.length;

        int max = 0;

        for (int i = 0; i < n; i++) {
            int l = i - 1;
            int r = i + 1;
            while (l >= 0 && heights[l] >= heights[i]) {
                --l;
            }

            while (r < n && heights[r] >= heights[i]) {
                ++r;
            }

            max = Math.max(max, (r - l - 1) * heights[i]);
        }

        return max;
    }*/

    public static void main(String[] args) {
        LeetCode84 code = new LeetCode84();
        System.out.println(code.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(code.largestRectangleArea(new int[]{2,4}));
    }

}
